#include<vector>
using namespace std;

class Solution {
private:
    void swap(vector<int>& nums,int left,int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

    void permute(vector<int> nums, int index,int & count) {
        if (index == nums.size()) {
            ++count;
            return;
        }

        for (int i = index; i < nums.size(); ++i) {
            if (nums[i] % (index+1) == 0 || (index+1) % nums[i] == 0) {
                swap(nums,index,i);
                permute(nums, index + 1, count);
                swap(nums, index, i);
            }
        }
    }
public:
    int countArrangement(int N) {
        vector<int> nums(N);
        for (int i = 0; i < N; ++i) {
            nums[i] = i + 1;
        }
        int count = 0;
        permute(nums, 0, count);
        return count;
    }
};